package leetcode.每日一题;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/7/11 22:34
 * @description：https://leetcode-cn.com/problems/sort-an-array/
 */
public class 排序数组 {
    @Test
    public void test() {
        Solution solution = new Solution();
        int[] ints = solution.sortArray(new int[]{5, 1, 1, 2, 0, 0});
        System.out.println(Arrays.toString(ints));
    }

    class Solution {
        public int[] sortArray(int[] nums) {
            quickSort(nums, 0, nums.length - 1);
            return nums;
        }

        private void quickSort(int[] nums, int left, int right) {
            if (left >= right) return;
            int l = left;
            int r = right;
            int pivot = nums[l];
            while (l < r) {
                while (l < r && nums[r] >= pivot) {
                    r--;
                }
                nums[l] = nums[r];
                while (l < r && nums[l] <= pivot) {
                    l++;
                }
                nums[r] = nums[l];
                nums[l] = pivot;
            }
            quickSort(nums, left, r - 1);
            quickSort(nums, r + 1, right);
        }
    }


}
